package algorithm;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

public class LongestSubsequence {
	private int maxsum = 0;
	private int begin = 0, end = 0;
	
	LongestSubsequence(){
		
	}
	
	LongestSubsequence(File file){
		try {
			Scanner sc = new Scanner(file);
			ArrayList<Integer> list = new ArrayList<Integer>();
			while(sc.hasNextInt()){
				list.add(sc.nextInt());
			}
			int temp = list.size();
			int[] arr = new int[temp];
			int i = 0;
			while(i != temp){
				arr[i] = list.get(i);
				i++;
			}
			maxsum = maxSubSum4(arr);
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	LongestSubsequence(String fileDirectory){
		this(new File(fileDirectory));
	}
	
	
	public int maxSubSum1(int[] arr){
		for(int i = 0; i < arr.length; i++){
			for(int j = i; j < arr.length; j++){
				int thissum = 0;
				int k = i;
				for(; k <= j; k++){
					thissum += arr[k];				
				}
				if(thissum > maxsum){
					maxsum = thissum;
					begin = i;
					end = j;
				}
			}
		}
		return maxsum;
	}
	
	public int maxSubSum2(int[] arr){
		for(int i = 0; i < arr.length; i++){
			int thissum = 0;
			for(int j = i; j < arr.length; j++){
				
				thissum += arr[j];
				if(thissum > maxsum){
					maxsum = thissum;
					begin = i;
					end = j;
				}
			}
		}
		return maxsum;
	}
	
	private int maxSumRec(int[] a, int left, int right){
		if(left == right)
			if(a[left] > 0)
				return a[left];
			else
				return 0;
		int center = (left + right) / 2;
		int maxLeftSum = maxSumRec(a, left, center);
		int maxRightSum = maxSumRec(a, center + 1, right);
		
		int maxLeftBorderSum = 0, leftBorderSum = 0;
		for(int i = center; i >= left; i--){
			leftBorderSum += a[i];
			if(leftBorderSum > maxLeftBorderSum)
				maxLeftBorderSum = leftBorderSum;
		}
		
		int maxRightBorderSum = 0, rightBorderSum = 0;
		for(int i = center + 1; i < right; i++){
			rightBorderSum += a[i];
			if(rightBorderSum > maxRightBorderSum){
				maxRightBorderSum = rightBorderSum;
			}
		}
		int aa = (maxLeftSum > maxRightSum) ? maxLeftSum : maxRightSum;
		int bb = maxLeftBorderSum + maxRightBorderSum;
		maxsum = (aa > bb) ? aa : bb;
		return maxsum;
	}
	
	public int maxSubSum3(int [] a){
		return maxSumRec(a, 0, a.length - 1);
	}
	
	public int maxSubSum4(int[] arr){
		int maxSum = 0, thissum = 0;
		boolean beginflag = true;
		for(int j = 0; j < arr.length; j++){
			thissum += arr[j];
			if(thissum > maxSum){
				maxSum = thissum;
				if(beginflag){
					begin = j;
					beginflag = false;
				}
				end = j;
			}
				
			else if(thissum < 0){
				thissum = 0;
				beginflag = true;
			}
				
		}
		
		maxsum = maxSum;
		return maxsum;
	}
	
	public int getMaxSum(){
		return maxsum;
	}
	
	public int getBegin(){
		return begin;
	}
	
	public int getEnd(){
		return end;
	}
}
